/* parallel_bucket_sort.c -- sort a list of evenly distributed numbers.
* The numbers are randomly generated and are evenly distributed in
* the range between 0 and 2*n
*
* Input: n, the number of numbers
*
* Output: the sorted list of numbers
*
* Note: Arrays are allocated using malloc. A single large array
* is used. Can use Scatter and Gather.
*
* Uses the bucket sort and selection sort algorithms.
*/
#include <cstdio>
#include <cstdlib> /* for random function */
#include "mpi.h"
#include <iostream>
#include <vector>
#include <cstring>
#include "insertion-sort.h"
#include "counting.h"
using std::cout;
using std::endl;
void Make_numbers(long long bigarray[], int n, int min, int max);
int hash(int min, int max, int buckets, long long value);
std::vector<std::vector<long long> >* separate_bucket(long long big_array[], int n, int min, int max, int buckets);

void concat_buckets(std::vector<std::vector<long long> >* vec, long long bigarray[], int n);

void Sequential_sort(long long [], int);
int Get_minpos(long long [], int);
void Put_numbers_in_bucket(long long [], long long [], int, int, int, int);

int main(int argc, char* argv[]) {
	int sort = 1; // Insertion
	long long * big_array = 0;
	int n=80; /* default is 80 elements to sort */
	long long number;
	int p;
	int my_rank;
	int i;
	int min, max;
	double start, stop; /* for timing */
	srand(time(NULL));
	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &p);
	MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
	cout << p << " processos iniciados." << endl;
	n = atoi(argv[1]); /* first parameter is the number of numbers */
	min = atoi(argv[2]);
	max = atoi(argv[3]);
	if(argc == 5)
		sort = atoi(argv[4]);
	int sendcounts[p];
	std::vector<std::vector<long long> >* vec ;
	int* disp = new int[p];
	if (my_rank == 0) {

		start = MPI_Wtime(); /* Timing */

		/* check if parameters are valid */

		/* make big array */
//		big_array = (long long *)malloc(n*sizeof(long long));
		big_array = new long long[n];
		if (big_array==NULL) {
			std::cerr << "Big_array malloc failed!!" << std::endl;
//			MPI_Abort( MPI_COMM_WORLD, 3 );
			exit(0);
		}
		cout << "Total elements: " << n << endl;
		Make_numbers(big_array, n, min, max);
		vec = separate_bucket(big_array, n, min, max, p);
		concat_buckets(vec, big_array, n);
		int offset = 0;
		for(int i = 0; i < p; i++) {
			sendcounts[i] = vec->at(i).size();
		}
		for(int i = 0; i < p; i++) {
			disp[i] = offset;
			offset +=sendcounts[i];
		}
	}
	/* Can use scatter if numbers are grouped in the big_array */
	int* recvcounts = new int[1];
//	int* recvcounts = (int*) calloc(p, sizeof(int));
	MPI_Scatter(sendcounts, 1, MPI_INT, recvcounts, 1, MPI_INT, 0, MPI_COMM_WORLD);
//	MPI_Bcast(sendcounts, p, MPI_INT, 0, MPI_COMM_WORLD);

	int n_local = recvcounts[0];
	long long* local_array = new long long[n_local];
	MPI_Scatterv(big_array, sendcounts, disp, MPI_LONG_LONG, local_array, n_local, MPI_LONG_LONG, 0, MPI_COMM_WORLD);

	if(sort == 1) { 
		cout << "Using insertion sort" << endl;
		insertion_sort(local_array, n_local);
	}
	else {
		cout << "Using counting sort" << endl;
		long long local_min = (((double) (max - min))/((double) p)) * my_rank;
		long long local_max = ((((double) (max - min))/((double) p)) * (my_rank+1)) + 1;
		counting_sort(local_array, n_local, local_min, local_max);
	}

	MPI_Gatherv(local_array, n_local, MPI_LONG_LONG, big_array, sendcounts, disp, MPI_LONG_LONG, 0, MPI_COMM_WORLD);
/*	if(my_rank == 0)
	for(int i = 0; i < n; i++)
		cout << big_array[i] << " ";
	cout << endl;*/
//	local_array, n_bar, MPI_LONG, 0, MPI_COMM_WORLD);

	/* Put_numbers_in_bucket(big_array, local_array, n, n_bar, p,
	my_rank); */

	//MPI_Gather(local_array, n_bar, MPI_LONG,
//	big_array, n_bar, MPI_LONG, 0, MPI_COMM_WORLD);

	stop = MPI_Wtime();

	if (my_rank==0) {
		printf("\n\nTime to sort using %d processes = %lf msecs\n",
		p, (stop - start)/0.001);
	}

	delete[] local_array;
	if (my_rank==0) delete[] big_array;
		MPI_Finalize();

} /* main */


void Make_numbers(long long big_array[], int n, int min, int max)
{
	/* Puts numbers in "buckets" but we can treat it otherwise */

	for (int i = 0; i < n; i++) {
			big_array[i] = random()%max + min;
	}
} 

int hash(int min, int max, int buckets, long long value) {
	double result = ((double) (buckets))*((double) (value - min) )/( (double) (max - min));
	if((int) result == buckets)
		return buckets-1;
//	return (buckets-1)*((value - min)/(max - min));
	return (int) result;
}

std::vector<std::vector<long long> >* separate_bucket(long long big_array[], int n, int min, int max, int buckets) {
	using std::vector;
	typedef vector<vector<long long> > vv;
	vv* vec = new vv();
	for(int i = 0; i < buckets; i++) {
		vec->push_back(vector<long long>());
	}
	for(int i = 0; i < n; i++) {
		int toPut = hash(min, max, buckets, big_array[i]);
		long long value = big_array[i];
		vec->at(toPut).push_back(value);
	}
	return vec;
}
void concat_buckets(std::vector<std::vector<long long> >* vec, long long big_array[], int n) {
	int buckets = vec->size();
	int offset = 0;
//	cout << buckets << " buckets criados." << endl;
	for(int i = 0; i < buckets; i++) {
		int vecsize = vec->at(i).size();
		if(vecsize != 0) {
			memcpy(&(big_array[offset]), &(vec->at(i).at(0)), sizeof(long long)*vecsize);
			offset+= vecsize;
//			cout << vecsize << " numeros copiados e offset vale" << offset << endl;
		}
	}
}

void Sequential_sort(long long array[] /* in/out */,
int size /* in */)
{
	/* Use selection sort to sort a list from smallest to largest */
	int eff_size, minpos;
	long long temp;

	for(eff_size = size; eff_size > 1; eff_size--) {
		minpos = Get_minpos(array, eff_size);
		temp = array[minpos];
		array[minpos] = array[eff_size-1];
		array[eff_size-1] = temp;
	}
}

/* Return the index of the smallest element left */
int Get_minpos(long long array[], int eff_size)
{
	int i, minpos = 0;

	for (i=0; i<eff_size; i++)
		minpos = array[i] > array[minpos] ? i: minpos;
	return minpos;
}


/*****************************************************************/
void Put_numbers_in_bucket(long long big_array[] /* in */,
long long local_array[] /* out */,
int n /* in */,
int n_bar /* in */,
int p /* in */,
int my_rank /* in */)
{
	/* Assume that numbers in big_array are evenly distributed at root,
	but are unsorted. Send numbers to the process that should have them.
	This version uses unsafe messaging and may fail in some cases!! */

	int i, q, bucket;
	MPI_Status status;

	if (my_rank == 0) {
		for (i=0; i<n; i++) {
			bucket = big_array[i]/(2*n_bar); /* Assume the range is 2*n */
			MPI_Send(&big_array[i], 1, MPI_LONG, bucket,
			0, MPI_COMM_WORLD);
			/* printf("P%d:%ld ", bucket, big_array[i]); */
		}
		/* printf("\n"); */
	}
	for (i=0; i<n_bar; i++) {
		MPI_Recv(&local_array[i], 1, MPI_LONG, MPI_ANY_SOURCE,
		0, MPI_COMM_WORLD, &status);
	}
}
